package com.da.javatest.niuke.jianzhi;

/**
 * @author chenlida
 * @date 2020/10/22 11:02
 * https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?
 * tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C30Solution {
    /**
     * 典型的动态规划。dp[n]代表以当前元素为截止点的连续子序列的最大和，如果dp[n-1]>0，dp[n]=dp[n]+dp[n-1]，
     * 因为当前数字加上一个正数一定会变大；如果dp[n-1]<0，dp[n]不变，因为当前数字加上一个负数一定会变小。
     * 使用一个变量max记录最大的dp值返回即可。
     */
    public static int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            array[i] += array[i - 1] > 0 ? array[i - 1] : 0;
            max = Math.max(max, array[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(FindGreatestSumOfSubArray(new int[] {6, -3, -2, 7, -15, 1, 2, 2}));
    }
}
